// Created by WXX on 2021/9/24 17:04
#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

class LRUCache {
public:

    struct Node {
        int key, val;
        Node *left, *right;

        Node(int _key, int _val): key(_key), val(_val), left(NULL), right(NULL) {}
    } *L, *R;
    unordered_map<int, Node*> hash;
    int n;

    LRUCache(int capacity) {
        n = capacity;
        L = new Node(-1, -1), R = new Node(-1, -1);
        L->right = R, R->left = L;
    }

    int get(int key) {
        if (!hash.count(key)) return -1;
        auto p = hash[key];
        remove(p);
        insert(p);
        return p->val;
    }

    void put(int key, int value) {
        if (hash.count(key)) {
            auto p = hash[key];
            p->val = value;
            remove(p);
            insert(p);
        } else {
            if (hash.size() == n) {  // 删除链尾元素
                auto p = R->left;
                remove(p);
                hash.erase(p->key);
                delete p;
            }
            Node *p = new Node(key, value);
            insert(p);
            hash[key] = p;
        }
    }

    void remove(Node *p) {  // 删除节点p
        p->left->right = p->right;
        p->right->left = p->left;
    }

    void insert(Node *p) {  // 在头结点中插入p
        p->right = L->right;
        p->left = L;
        L->right->left = p;
        L->right = p;
    }
};

int main() {


    return 0;
}
